import java.util.*;
/**
 * 
 * 输出二叉树的右视图
 * 
 * 描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围： 
0
≤
n
≤
10000
0≤n≤10000
要求： 空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
n
)
O(n)

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

所以对应的输出为[1,3,5]。

 */
public class 输出二叉树的右视图 {
    
    public static void main(String[] args) {
        

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
//将xianxu节点的值映射到相应的中序节点的下标。
        for (int i = 0; i < inOrder.length; i++) {
            map.put(inOrder[i], i);
        }
        //开始构建二叉树。
        build(preOrder, inOrder, 0, preOrder.length - 1, 0);

        //创建放回答案的数组
        int[] temp = new int[ans.size()];

        //将值传入数组。
        for (int i = 0; i < ans.size(); i++) {
            temp[i] = ans.get(i);
        }

        return temp;
    }

    public void build(int[] preOrder, int[] inOrder, int left, int right, int i) {
        if (left > right) {
            return;
        }
        int index = map.get(preOrder[j++]);
        //构建左子树
        build(preOrder, inOrder, left, index - 1, i + 1);
        //构建右子树
        build(preOrder, inOrder, index + 1, right, i + 1);
        //存储第i层的最右边的那个节点。
        ans.put(i, inOrder[index]);
    }

    private static HashMap<Integer, Integer> ans = new HashMap<>();
    private static HashMap<Integer, Integer> map = new HashMap<>();
    private static int j = 0;
}
